Concerning the NP (Nondeterministic Polynomial)-hard problem of localizing link failures from end-to-end measurement in communication network, a new tomography method which relaxes the Boolean constraints was proposed. Firstly, the relationship between path state and link state in a network was modeled as Boolean algebraic equations, and the essence of localizing failures was treated as an optimization problem under the constraints of these equations. Then the NP property was derived from the binary states (normal/failed) of link state in the optimization problem. Therefore, by relaxing the Boolean constraints, the proposed method simply transformed the problem into a Linear Programming (LP) problem, which can be easily solved by any LP solver to get the set of failed links. Simulation experiments were conducted to identity link failures in real network topologies. The experimental results show that the false negative rate of the proposed method is 5%-30% lower than that of the classical heuristic algorithm TOMO (TOMOgraphy).